題目

xLimit = n;
yLimit = m;
population = pij：坐落在(i, j)的人口數;
distance = r：醫院覆蓋距離;
(u, v)：給定的醫院座標

第一種演算法

建立一個存各城鎮人口數的陣列：populationArray[xLimit][yLimit] = {0}
coverPopulation = 0    // 蓋這間醫院所覆蓋到的人口數

// 掃過所有在xLimit X yLimit中的點
for i in range (0 ~ xLimit)
    for j in range (0 ~ yLimit)
        if abs(u - i) + abs(v - j) <= distance
			coverPopulation += populationArray[i][j]

Time complexity
O(1 + xLimit * yLimit) = O(xLimit * yLimit)

第二種演算法

這個方法是將舉行切成四等份：

// 矩形左上角
for i in range (從u - 1開始往左減, 在|i – u| <= distance內 && i >= 0)
	for j in range (從v開始, 在|j - v| <= distance內 && |i - u| + |j - v| <= distance內 && j <= yLimit)
		coverPopulation += populationArray[i][j]
// 矩形右上角
for i in range (從u開始往右加, 在|i – u| <= distance內 && i <= xLimit)
	for j in range (從v開始往上加, 在|j - v| <= distance內 && j <= yLimit)
		coverPopulation += populationArray[i][j]
// 矩形左下角
for i in range (從u - 1開始往左減, 在|i – u| <= distance內 && i >= 0)
	for j in range (從v – 1開始往下減, 在|j - v| <= distance內 && j >= 0)
		coverPopulation += populationArray[i][j]
// 矩形右下角
for i in range (從u開始往右加, 在|i – u| <= distance內 && i <= xLimit)
	for j in range (從v - 1開始往下減, 在|j - v| <= distance內 && j >= 0)
		coverPopulation += populationArray[i][j]

Time complexity
最多跑distance * distance次，所以 big O 為 O(distance^2)

在第一種演算法中，需要計算地圖上每一個點是否在給定醫院座標的範圍內，因此必須計算xLimit * yLimit次。
而在第二種演算法中，由於 for 迴圈已經限制要討論的座標範圍，因此最多只需討論distance * distance次就能計算出所覆蓋的人口數。
xLimit * yLimit >= distance * distance，所以第二種演算法更有效率。

而這樣的核心架構可以衍生出第二題：找出能造福最多民眾的醫院院址，計算其覆蓋的民眾總人數，並將之輸出。

輸入輸出格式：

其實這題並不難，按照上述第二種演算法即可（第一種演算法可能會面臨 time limit exceed 的問題)，不過這題 tricky 的地方在於他輸入的部分，第 2 行至第 m + 2 行所輸入的資料為每行固定 y 座標，因此當我們把輸入的座標 (i, j) 城鎮的人口數存進陣列(populationArray)時，不能用我最熟悉的 i 代表 x 座標、y 代表 y 座標：

而是要將 i, j 所表示的反過來：

我在寫的時候因為這個輸入格式沒看清楚卡了超久..題目真的要看清楚ㄚ！